Simplificació de llenguatges

Demostreu les igualtats següents entre llenguatges:

\{w\in \{a,b\}^* \mid aw=wb\}=\emptyset.
\{w\in \{a,b\}^* \mid abw=wab\}=\{ab\}^*.

Alerta

\{ab\}^* no és un lapsus, no hi ha “,” entre a i b.
\{xy\in \{a,b\}^* \mid |x|_a=|y|_a\}=\{w\in \{a,b\}^*\mid |w|_a\in 2\mathbb N\}.
\{xy\in \{a,b\}^* \mid |x|_a=|y|_b\}=\{a,b\}^*.
\{xy\in \{a,b\}^* \mid |x|_{aa}=|y|_b\}=\{a,b\}^*.
\{w\in \{0,1\}^* \mid \mathtt{value}_2(ww^R)\in 3\mathbb N\}=\{0,1\}^*

Observeu que la notació \{xy\in A \mid P(x,y)\}, per un conjunt A i un predicat P, és una forma abreujada de descriure el conjunt \{w\in A \mid \exists x,y\ w=xy \land P(x,y)\}.

Altres enllaços